<!doctype html>
<html lang="en">

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  
  <meta name="generator" content="Hugo 0.98.0" />

  
  <meta name="description" content="走在通往幸福的路上">
  

  
  <link rel="apple-touch-icon" sizes="180x180" href="https://blog.v5u.win/apple-touch-icon.png">

  
  <link rel="icon" type="image/png" sizes="32x32" href="https://blog.v5u.win/favicon-32x32.png">

  
  <link rel="icon" type="image/png" sizes="16x16" href="https://blog.v5u.win/favicon-16x16.png">

  
  <link rel="manifest" href="https://blog.v5u.win/site.webmanifest">

  
  <link rel="mask-icon" href="https://blog.v5u.win/safari-pinned-tab.svg" color="">

  <meta name="msapplication-TileColor" content="">

  <meta name="theme-color" content="">

  
  <link rel="stylesheet" href="https://blog.v5u.win/css/bootstrap.min.css" />

  
  <title>数据结构与算法1-复杂度分析1 | 为吾优</title>
  

  <style>
body {
  min-width: 300px;
}

.custom-navbar {
  margin-bottom: 1em;
  height: 60px;
}

.custom-navbar a {
  display: inline-block; 
  padding: 18px 0;
  margin-right: 1em; 
  font-weight: bold; 
}

.custom-navbar a:hover,
.custom-navbar a:focus {
  text-decoration: none; 
}

@media print {
  .custom-navbar {
    display: none;
  }
}

article {
  padding-bottom: 1em;
}

img {
  max-width: 100%;
}


body {
  background-color: #fff;
}



body {
  color: #212529;
}



a {
  color: #007bff;
}



a:hover,
a:focus {
  color: #0056b3;
}



.custom-navbar {
  background-color: #212529;
}



.custom-navbar a {
  color: rgba(255,255,255,.75);
}



.custom-navbar a:hover,
.custom-navbar a:focus {
  color: rgba(255,255,255,1);
}



.container {
  max-width: 800px;
}





</style>
</head>

<body>
  <nav class="custom-navbar">
  <div class="container">
    
    <a href="/">文章</a>
    
    <a href="/tags/">标签</a>
    
    <a href="/about/">关于</a>
    
    <a href="/index.xml">RSS</a>
    
  </div>
</nav>
  
  <div class="container">
    <article>
      <h1>数据结构与算法1-复杂度分析1</h1>
<p>为什么需要复杂度分析？</p>
<h4 id="有两种估算方法1事后统计法-2大o复杂度表示法">有两种估算方法：1.事后统计法 2.大O复杂度表示法</h4>
<ol>
<li>事后统计法: 把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小</li>
</ol>
<ul>
<li>
<p>测试结果非常依赖测试环境</p>
</li>
<li>
<p>测试结果受数据规模的影响很大</p>
</li>
</ul>
<ol start="2">
<li>
<p>我们需要一个不用具体的测试数据来测试，就可以粗略的估计计算法的执行效率的方法——大O复杂度表示法</p>
<p>从CPU角度看，代码的执行类似这种操作：读数据——运算——写数据。</p>
<p>所有代码的执行时间T(n)与每行代码的执行次数n成正比。T(n)=O(f(n)),例：T(n)=O(2n+2),T(n)=O(2n²+2n+3)</p>
<p>大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫，渐进时间复杂度，简称时间复杂度。T(n) = O(n)； T(n) = O(n²)。</p>
</li>
</ol>
<h4 id="时间复杂度分析">时间复杂度分析</h4>
<ol>
<li>只关注循环执行次数最多的一段代码：核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度</li>
<li>加法法则：总复杂度等于量级最大的那段代码的复杂度</li>
<li>乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积</li>
</ol>
<h4 id="几种常见时间复杂度实例分析">几种常见时间复杂度实例分析</h4>
<pre><code>常量阶O(1)	对数阶O(logn)	线性阶O(n)	线性对数阶O(nlogn)

指数阶O(2^n)		阶乘阶O(n!)
</code></pre>
<p>粗略分为两类：多项式量级和非多项式量级，非多项式量级只有两个：O(2^n)和O(n!)。</p>

    </article>
  </div>

  
  
  

  
</body>

</html>